package main

var factorialMap = map[int]int{
	0: 1,
}
var N int

func factorial(n int) int {
	if n <= N {
		return factorialMap[n]
	}
	f := factorialMap[N]
	for i := N + 1; i <= n; i++ {
		f *= i
		factorialMap[i] = f
	}
	N = n
	return factorialMap[n]
}

var order int
var result string

func getPermutation(n int, k int) string {
	if n == 1 {
		return "1"
	}
	order = 0
	result = ""
	backtrack(nil, n, k)
	return result
}

func backtrack(sb []byte, n int, k int) bool {
	if len(sb) == n {
		order++
		if order == k {
			result = string(sb)
			return true
		}
		return false
	}
	valid := make([]bool, n+1)
	for _, b := range sb {
		i := b - '0'
		valid[i] = true
	}
	// 以 i 开头的排列有 m 个
	m := factorial(n - len(sb) - 1)
	for i := 1; i <= n; i++ {
		if valid[i] {
			continue
		}
		// 以 i 开头的排列最大序号为 order + m
		if order+m < k {
			order += m
			continue
		}
		sb = append(sb, byte(i)+'0')
		if backtrack(sb, n, k) {
			return true
		}
		sb = sb[:len(sb)-1]
	}
	return false
}

func main() {
	println(getPermutation(3, 3))
	println(getPermutation(4, 9))
	println(getPermutation(3, 1))
}
